We study the asymmetric binary matrix partition problem that was recentlyintroduced by Alon et al. (WINE 2013) to model the impact of asymmetricinformation on the revenue of the seller in take-it-or-leave-it sales.Instances of the problem consist of an $n \times m$ binary matrix $A$ and aprobability distribution over its columns. A partition scheme $B=(B_1,...,B_n)$consists of a partition $B_i$ for each row $i$ of $A$. The partition $B_i$ actsas a smoothing operator on row $i$ that distributes the expected value of eachpartition subset proportionally to all its entries. Given a scheme $B$ thatinduces a smooth matrix $A^B$, the partition value is the expected maximumcolumn entry of $A^B$. The objective is to find a partition scheme such thatthe resulting partition value is maximized. We present a $9/10$-approximationalgorithm for the case where the probability distribution is uniform and a$(1-1/e)$-approximation algorithm for non-uniform distributions, significantlyimproving results of Alon et al. Although our first algorithm is combinatorial(and very simple), the analysis is based on linear programming and dualityarguments. In our second result we exploit a nice relation of the problem tosubmodular welfare maximization.
展开▼
机译：我们研究了Alon等人最近引入的非对称二进制矩阵分配问题。 （WINE 2013），以不对称信息对卖方接受或离开销售中的收入的影响进行建模。问题的实例包括：$ n \ times $$二进制矩阵$ A $和概率分布它的列。分区方案$ B =（B_1，...，B_n）$由$ A $的每一行$ i $组成的分区$ B_i $。分区$ B_i $充当行$ i $上的平滑运算符，该分区将每个分区子集的期望值按比例分配给其所有条目。给定方案$ B $产生平滑矩阵$ A ^ B $，则分区值是$ A ^ B $的预期最大列条目。目的是找到一种分区方案，以使最终的分区值最大化。对于概率分布均匀的情况，我们提出了9/10美元的近似算法，对于非均匀分布的情况，我们提出了（$ 1-1 / e）$近似算法，这大大改善了Alon等人的结果。尽管我们的第一个算法是组合的（并且非常简单），但是分析是基于线性规划和对偶参数的。在我们的第二个结果中，我们利用了问题与次模块化福利最大化之间的良好关系。
展开▼
